//
// Created by user on 2022/3/1.
//
#include <string>
#include <deque>
using namespace std;
// 双端队列
string reverseWords(string s) {
    int left = 0, right = s.size() - 1;
    // 去掉字符串开头的空白字符
    while (left <= right && s[left] == ' ') ++left;

    // 去掉字符串末尾的空白字符
    while (left <= right && s[right] == ' ') --right;

    deque<string> deque;
    string word;
    while (left <= right) {
        char c  = s[left];
        if (c != ' ') {
            word += c;
        } else if (word.size()) {
            deque.push_front(word);
            word = "";
        }
        left++;
    }
    deque.push_front(word);

    string ans;
    while (!deque.empty()) {
        ans += deque.front();
        deque.pop_front();
        if (!deque.empty()) ans += " ";
    }
    return ans;
}